1788D - Moving Dots - CodeForces Solution

#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#define ll long long

using namespace std;

ll s, t, n, temp, mini, maxi, diff, m, x, y, gain, result, w, curr, mask, ss, tt, k;
ll u, l, d, r, b1, b2;
vector<ll> a1, p1, p2, p3, indarr, weights;
vector<pair<ll,ll>> a;
vector<vector<ll>> graph, edges;
vector<priority_queue<ll>> graph1, graph2;
vector<vector<ll>> graph3;
vector<ll> dp, dp2, dp3;
vector<vector<ll>> prev_v;
set<ll> path;
set<ll> used;
vector<ll> prime;
map<ll,ll> indices, dp4;
pair<ll,ll> curr_pair;
vector<ll> result_vec;
bool possible;
vector<ll> sc;
vector<ll> parent;


ll modulus2 = 998244353;
ll modulus3 = 1000000007;

void SieveOfEratosthenes(int n) {
    for (ll i = 0; i < n+1; i++) prime.push_back(i);
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == p) {
            for (int i = p * p; i <= n; i += p) prime[i] = p;
        }
    }
}

ll mod_inv(ll i) {
  return i <= 1 ? i : modulus2 - (long long)(modulus2/i) * mod_inv(modulus2 % i) % modulus2;
}

void dp_helper(ll v) {
    if (graph[v].size() == 1 && graph[v][0] == parent[v]) {
        if (a1[v] == 1) sc[v] = 1;
        else sc[v] = 0;
        return;
    }
    for (ll i : graph[v]) {
        if (i == parent[v]) continue;
        parent[i] = v;
        dp_helper(i);
        sc[v] += sc[i];
    }
    if (a1[v] == 1) sc[v]++;
}

ll sum_digits(ll num) {
    if (num == 0) return 0;
    else return num % 10 + sum_digits(num / 10);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n; a1 = {0}; p1 = {}; temp = 1;
    
    for (int i = 0; i <= n; i++) {
        p1.push_back(temp); temp *= 2; temp %= modulus3;
    }
    
    for (int i = 0; i < n; i++) {
        cin >> temp; a1.push_back(temp);
    }
    
    result = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            x = a1[i]; y = a1[j]; diff = x - y;
            l = y - diff; r = x + diff;
            d = max((ll)(lower_bound(a1.begin(), a1.end(), l) - a1.begin()) - 1, (ll)0);
            u = lower_bound(a1.begin(), a1.end(), r) - a1.begin();
            // cout << d << " " << u << " " << i << " " << j << " " << d + n - u + 1 << "\n";
            result += p1[d + n - u + 1]; result %= modulus3;
        }        
    }
    cout << result << "\n";
    
    
    return 0;
}